//
// Created by ASUS on 2024/5/20/星期一.
//
#include <bits/stdc++.h>
using namespace std;

//字符串中至多一个字母出现奇数次，则称其为最美字符串。字符集：a-j
long long wonderfulSubstrings(string word) {
	int n = word.length();
	unordered_map<int, long long> cnt;
	cnt[0] = 1;
	long long ans = 0;
	int pre = 0;
	for (int i = 0; i < n; i++) {
		pre ^= (1 << (word[i] - 'a'));
		for (int d = 0; d < 10; d++) {
			ans += cnt[pre ^ (1 << d)];
		}
		ans += cnt[pre];
		cnt[pre]++;
	}
	return ans;
}
//优化版，使用数组代替哈希表
long long wonderfulSubstrings1(string word) {
	int n = word.length();
	vector<int> cnt(1<<10);
	cnt[0]=1;
	long long ans=0;
	int pre=0;
	for(int i=0;i<n;i++){
		pre^=(1<<(word[i]-'a'));
		for(int d=0;d<10;d++){
			ans+=cnt[pre^(1<<d)];
		}
		ans+=cnt[pre];
		cnt[pre]++;
	}
	return ans;
}